package org.example.queue;

public class Heap {
    // 向下调整：用于构建大根堆（每次选择较大的孩子）
    public static void shiftDown(int[] arr, int parent){
        int child=parent*2+1;
        int size=arr.length;
        while(child<size){
            // 如果右孩子存在且更大，则 child 指向右孩子
            if (child+1<size && arr[child+1]>arr[child]){
                child+=1;
            }
            // 如果父节点 >= 较大的孩子，堆已满足
            if (arr[parent]>=arr[child]){
                break;
            }else{
                int t=arr[parent];
                arr[parent]=arr[child];
                arr[child]=t;
                //继续向下调整
                parent=child;
                child=parent*2+1;
            }
        }
    }
    //创建大根堆
    public static void createHeap(int[] arr){
        //最后一个非叶子节点的下标
        //      1 (0)
        //       / \
        //    2(1) 3(2)
        //     / \  /
        // 4(3)5(4)6(5)
        //最后一个节点是 6，下标 5
        //它的父节点是 (5 - 1)/2 = 4/2 = 2 → 下标 2，值为 3
        //所以最后一个非叶子节点是 下标为 2 的节点 3
        //右移一位等于除以2
        int root=(arr.length-2)>>1;
        //从最后一个非叶子结点开始，向上调整到跟
        for (;root>=0;root--){
            shiftDown(arr,root);
        }
    }
    // 测试
    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 8, 7, 6};
        System.out.println("初始数组：");
        printArray(arr);
        createHeap(arr);
        System.out.println("建大根堆后：");
        printArray(arr);
    }
    public static void printArray(int[] array) {
        for (int v : array) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}
